﻿// 187. 导弹防御系统.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>
#include <queue>
#include <algorithm>
#include <cstring>

using namespace std;


/*
https://www.acwing.com/problem/content/189/

为了对抗附近恶意国家的威胁，R 国更新了他们的导弹防御系统。

一套防御系统的导弹拦截高度要么一直 严格单调 上升要么一直 严格单调 下降。

例如，一套系统先后拦截了高度为 3 和高度为 4 的两发导弹，那么接下来该系统就只能拦截高度大于 4 的导弹。

给定即将袭来的一系列导弹的高度，请你求出至少需要多少套防御系统，就可以将它们全部击落。

输入格式
输入包含多组测试用例。

对于每个测试用例，第一行包含整数 n，表示来袭导弹数量。

第二行包含 n 个不同的整数，表示每个导弹的高度。

当输入测试用例 n=0 时，表示输入终止，且该用例无需处理。

输出格式
对于每个测试用例，输出一个占据一行的整数，表示所需的防御系统数量。

数据范围
1≤n≤50
输入样例：
5
3 5 2 4 1
0
输出样例：
2
样例解释
对于给出样例，最少需要两套防御系统。

一套击落高度为 3,4 的导弹，另一套击落高度为 5,2,1 的导弹。


40
15 30 40 34 12 23 24 1 31 35 22 37 29 21 3 13 33 5 25 32 8 2 4 36 7 38 10 27 18 6 28 26 17 16 9 20 11 39 19 14
40
21 35 2 15 13 14 33 11 22 19 12 9 31 18 5 20 25 28 10 23 1 27 6 24 16 26 29 34 39 7 40 8 17 36 30 3 37 32 38 4
50
42 20 17 25 8 2 34 27 39 29 11 1 4 16 24 21 10 37 22 12 18 28 9 50 19 5 36 13 33 15 7 47 32 31 26 14 49 6 44 41 40 23 35 45 43 46 30 48 3 38
10
1 10 2 9 3 8 4 7 5 6
10
1 2 3 4 5 6 7 8 9 10
10
10 9 8 7 6 5 4 3 2 1
25
1 21 14 11 12 6 13 5 19 17 9 23 16 18 7 22 8 20 15 10 25 3 24 2 4
25
6 11 8 18 12 23 16 3 4 20 7 21 5 24 22 15 25 13 2 19 14 10 9 1 17
0


6
6
8
2
1
1
5
5

5
1 2 3 4 5 
5
1 2 3 2 1

*/

const int N = 90;
int arr[N];
int n;
int ans = 0x3f3f3f3f;

int upa[N]; int upx;
int doa[N]; int dox;

void dfs(int x) {
	if (upx + dox >= ans) return;
	if (x > n) {
		ans = min(ans, upx + dox);
		return;
	}
	int upback[N]; int upbackx = upx;
	memcpy(upback, upa, sizeof upback);

	int val = arr[x]; int suc = 0;
	//尝试放入上升
	for (int i = 0; i < upx; i++) {
		if (val > upa[i]) {
			upa[i] = val; suc = 1; break;
		}
	}

	if(1==suc){
		dfs(x + 1);
		//还原
		memcpy(upa, upback,sizeof upback);
		upx = upbackx;
	}
	else {
		//放入不了 则新加一个上升队列;
		upa[upx++] = val;
		dfs(x + 1);
		//还原
		memcpy(upa, upback, sizeof upback);
		upx = upbackx;
	}


	//尝试放入下降 
	suc = 0;
	int doback[N]; int dobackx = dox;
	memcpy(doback, doa, sizeof doback);
	for (int i = 0; i < dox; i++) {
		if (val < doa[i]) {
			doa[i] = val; suc = 1; break;
		}
	}
	if (1 == suc) {
		dfs(x + 1);
		//还原
		memcpy(doa, doback, sizeof doback);
		dox = dobackx;
	}
	else {
		doa[dox++] = val;
		dfs(x + 1);
		//还原
		memcpy(doa, doback, sizeof doback);
		dox = dobackx;
	}

	return;
}


void solve() {
	ans = 0x3f3f3f3f;
	memset(upa, 0x3f, sizeof upa);
	memset(doa, 0, sizeof doa);

	dfs(1);

	cout << ans << endl;
}

int main()
{
	while (cin >> n) {
		if (0 == n) break;
		for (int i = 1; i <= n; i++) {
			cin >> arr[i];
		}

		solve();
	}
	

	return 0;
}

 